#define _CRT_SECURE_NO_WARNINGS
//dfs
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        return dfs(root->left, root->right);
    }
    bool dfs(TreeNode* p, TreeNode* q) {
        if (!p && !q) return true;
        if (!p || !q) return false;
        return p->val == q->val && dfs(p->left, q->right) && dfs(p->right, q->left);
    }
};
//bfs
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        queue<TreeNode*> q;
        q.push(root->left);
        q.push(root->right);
        while (!q.empty()) {
            TreeNode* right = q.front();
            q.pop();
            TreeNode* left = q.front();
            q.pop();
            if (!right && !left) continue;
            if (!right || !left) return false;
            if (right->val != left->val) return false;
            q.push(right->right);
            q.push(left->left);
            q.push(right->left);
            q.push(left->right);
        }
        return true;
    }
};